package UnionSearchSet;

import java.util.Arrays;

/**
 * @Author Fizz Pu
 * @Date 2020/9/1 下午5:53
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */
public class UnionSearchSet {
    private int[] roots;

    // 初始化时，每个元素单独为一个集合
    public UnionSearchSet(int n) {
        roots = new int[n];
        for (int i = 0; i < n; ++i) {
            roots[i] = i;
        }
    }

    // 合并
    public void union(int ele1, int ele2) {
        int x = find(ele1);
        int y = find(ele2);
        if (x != y) { // 不是同一个集合就合并
            roots[x] = y; // 相当于x的父亲是y
        }
    }

    // 查找
    // 利用路径压缩优化查找算法
    public int find(int element) {
        if (element == roots[element]) {
            return element;
        }
        // return  find(roots[element]); // 优化
        return roots[element] = find(roots[element]); // 直接保存根
    }

    // 统计集合个数,利用集合去重实现
    // 优化实现
    public int countSetNumber() {
        /*int len = roots.length;
        HashSet<Integer> hashset = new HashSet<>(len);
        for (int i = 0; i < len; ++i) {
            hashset.add(find(i));
        }
        return hashset.size();*/
        int count = 0;
        for(int i = 0; i < roots.length; ++i){
            if(roots[i] == i)++count;
        }
        return count;
    }


    @Override
    public String toString() {
        return "UnionSearchSet{" +
                "roots=" + Arrays.toString(roots) +
                '}';
    }
}
